package algorithms.queue;

/**
 * 基于单向链表的单向队列
 * 
 * @author syx
 *
 */
public class Queue<T> {
	private Node<T> cur;
	private Node<T> head;
	/**
	 * 使用tail指向尾节点，方便添加元素到队列
	 */
	private Node<T> tail;

	public Queue() {

	}

	public Queue(Node<T> node) {
		this.head = node;
		while (node.getNext() != null) {
			node = node.getNext();
		}
		this.tail = node;
	}

	/**
	 * 入队
	 * 
	 * @param node
	 */
	public void Enqueue(Node<T> node) {
		if (this.head == null) {
			this.head = node;
		}
		this.tail.setNext(node);
		while (node.getNext() != null) {
			node = node.getNext();
		}
		this.tail = node;
	}

	/**
	 * 出队(删除)
	 * 
	 * @return
	 */
	public Node<T> dequeue() {
		Node<T> n = this.head;
		this.head = this.head.getNext();
		n.setNext(null);
		return n;
	}

	/**
	 * 取下一个值
	 * 
	 * @return
	 */
	public Node<T> head() {
		return cur = cur == null ? this.head : cur.getNext();
	}

	public boolean isEmpty() {
		return this.head == null;
	}

	public void clear() {
		Node<T> node = this.head;
		if (node != null) {
			Node<T> next = node.getNext();
			this.head = null;
			while (next != null) {
				node = next;
				next = next.getNext();
				node.setNext(null);
				node = null;
			}
		}

	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Node<T> node = this.head;
		while (node != null) {
			sb.append(node.getKey()).append(",");
			node = node.getNext();
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1).toString() : "[]";
	}

	public Node<T> getHead() {
		return head;
	}

	public void setHead(Node<T> head) {
		this.head = head;
	}

	public Node<T> getTail() {
		return tail;
	}

	public void setTail(Node<T> tail) {
		this.tail = tail;
	}
}
